# coding: utf-8
'''
Created on 25/06/2013

@author: vagner
'''

def get_jacobi_symbol(a,n):
    if a == 0 or a == 1:
        return a
    if a == 2:
        if (n % 8 ==3) or (n % 8==5):
            return -1
        else: return 1
    if a % 2==0:
        return get_jacobi_symbol(2,n) * get_jacobi_symbol(a//2,n)
    if a >= n:
        return get_jacobi_symbol(a%n,n)
    if a % 4 == 3 and n%4 == 3:
        return (-1)*get_jacobi_symbol(n,a)
    else:
        return get_jacobi_symbol(n,a)